//
//  KDTree.hpp
//  RayTracer
//
//  Created by 俞云康 on 4/14/16.
//  Copyright © 2016 yushroom. All rights reserved.
//

#ifndef KDTree_hpp
#define KDTree_hpp

#include "Primitive.hpp"

struct KDTreeNode;

class KDTree {
public:
    KDTree(const vector<shared_ptr<GeometricPrimitive>> &p,
           int isectCost = 80,
           int traversalCost = 1,
           float emptyBonus = 0.5f,
           int maxPrims = 1,
           int maxDepth = -1);
    ~KDTree();
    AABB worldBounds() const { return bounds; }
    bool intersect(const Ray& ray, HitInfo * isect) const;
    bool intersect(const Ray& ray) const;
    
private:
    const int isectCost, traversalCost, maxPrims;
    const float emptyBonus;
    vector<shared_ptr<GeometricPrimitive>> primitives;
    vector<int> primitiveIndices;
    KDTreeNode *nodes;
    int nAllocedNodes, nextFreeNode;
    AABB bounds;
    
    void buildTree(int nodeNum,
                   const AABB& bounds,
                   const vector<AABB>& primBounds,
                   int *primNums,
                   int nPrims,
                   int depth,
                   const unique_ptr<BoundEdge[]> edges[3],
                   int *prims0,
                   int *prims1,
                   int badRefines = 0);
};

#endif /* KDTree_hpp */
